/*
 * Copyright (c) 2007, 2015, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
/*
 * Copyright 2001-2006 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: UnionIterator.java 337874 2004-02-16 23:06:53Z minchau $
 */

package com.sun.org.apache.xalan.internal.xsltc.dom;

import com.sun.org.apache.xalan.internal.xsltc.DOM;
import com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary;
import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
import com.sun.org.apache.xml.internal.dtm.ref.DTMAxisIteratorBase;

/**
 * <p><code>MultiValuedNodeHeapIterator</code> takes a set of multi-valued
 * heap nodes and produces a merged NodeSet in document order with duplicates
 * removed.</p>
 * <p>Each multi-valued heap node (which might be a
 * {@link org.apache.xml.dtm.DTMAxisIterator}, but that's  not necessary)
 * generates DTM node handles in document order.  The class
 * maintains the multi-valued heap nodes in a heap, not surprisingly, sorted by
 * the next DTM node handle available form the heap node.</p>
 * <p>After a DTM node is pulled from the heap node that's at the top of the
 * heap, the heap node is advanced to the next DTM node handle it makes
 * available, and the heap nature of the heap is restored to ensure the next
 * DTM node handle pulled is next in document order overall.
 *
 * @author Jacek Ambroziak
 * @author Santiago Pericas-Geertsen
 */
public abstract class MultiValuedNodeHeapIterator extends DTMAxisIteratorBase {
  /** wrapper for NodeIterators to support iterator
   comparison on the value of their next() method
   */

  /**
   * An abstract representation of a set of nodes that will be retrieved in
   * document order.
   */
  public abstract class HeapNode implements Cloneable {

    protected int _node, _markedNode;
    protected boolean _isStartSet = false;

    /**
     * Advance to the next node represented by this {@link HeapNode}
     *
     * @return the next DTM node.
     */
    public abstract int step();


    /**
     * Creates a deep copy of this {@link HeapNode}.  The clone is not
     * reset from the current position of the original.
     *
     * @return the cloned heap node
     */
    public HeapNode cloneHeapNode() {
      HeapNode clone;

      try {
        clone = (HeapNode) super.clone();
      } catch (CloneNotSupportedException e) {
        BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
            e.toString());
        return null;
      }

      clone._node = _node;
      clone._markedNode = _node;

      return clone;
    }

    /**
     * Remembers the current node for the next call to {@link #gotoMark()}.
     */
    public void setMark() {
      _markedNode = _node;
    }

    /**
     * Restores the current node remembered by {@link #setMark()}.
     */
    public void gotoMark() {
      _node = _markedNode;
    }

    /**
     * Performs a comparison of the two heap nodes
     *
     * @param heapNode the heap node against which to compare
     * @return <code>true</code> if and only if the current node for this heap node is before the
     * current node of the argument heap node in document order.
     */
    public abstract boolean isLessThan(HeapNode heapNode);

    /**
     * Sets context with respect to which this heap node is evaluated.
     *
     * @param node The new context node
     * @return a {@link HeapNode} which may or may not be the same as this <code>HeapNode</code>.
     */
    public abstract HeapNode setStartNode(int node);

    /**
     * Reset the heap node back to its beginning.
     *
     * @return a {@link HeapNode} which may or may not be the same as this <code>HeapNode</code>.
     */
    public abstract HeapNode reset();
  } // end of HeapNode

  private static final int InitSize = 8;

  private int _heapSize = 0;
  private int _size = InitSize;
  private HeapNode[] _heap = new HeapNode[InitSize];
  private int _free = 0;

  // Last node returned by this MultiValuedNodeHeapIterator to the caller of
  // next; used to prune duplicates
  private int _returnedLast;

  // cached returned last for use in gotoMark
  private int _cachedReturnedLast = END;

  // cached heap size for use in gotoMark
  private int _cachedHeapSize;


  public DTMAxisIterator cloneIterator() {
    _isRestartable = false;
    final HeapNode[] heapCopy = new HeapNode[_heap.length];
    try {
      MultiValuedNodeHeapIterator clone =
          (MultiValuedNodeHeapIterator) super.clone();

      for (int i = 0; i < _free; i++) {
        heapCopy[i] = _heap[i].cloneHeapNode();
      }
      clone.setRestartable(false);
      clone._heap = heapCopy;
      return clone.reset();
    } catch (CloneNotSupportedException e) {
      BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
          e.toString());
      return null;
    }
  }

  protected void addHeapNode(HeapNode node) {
    if (_free == _size) {
      HeapNode[] newArray = new HeapNode[_size *= 2];
      System.arraycopy(_heap, 0, newArray, 0, _free);
      _heap = newArray;
    }
    _heapSize++;
    _heap[_free++] = node;
  }

  public int next() {
    while (_heapSize > 0) {
      final int smallest = _heap[0]._node;
      if (smallest == END) { // iterator _heap[0] is done
        if (_heapSize > 1) {
          // Swap first and last (iterator must be restartable)
          final HeapNode temp = _heap[0];
          _heap[0] = _heap[--_heapSize];
          _heap[_heapSize] = temp;
        } else {
          return END;
        }
      } else if (smallest == _returnedLast) {       // duplicate
        _heap[0].step(); // value consumed
      } else {
        _heap[0].step(); // value consumed
        heapify(0);
        return returnNode(_returnedLast = smallest);
      }
      // fallthrough if not returned above
      heapify(0);
    }
    return END;
  }

  public DTMAxisIterator setStartNode(int node) {
    if (_isRestartable) {
      _startNode = node;
      for (int i = 0; i < _free; i++) {
        if (!_heap[i]._isStartSet) {
          _heap[i].setStartNode(node);
          _heap[i].step();     // to get the first node
          _heap[i]._isStartSet = true;
        }
      }
      // build heap
      for (int i = (_heapSize = _free) / 2; i >= 0; i--) {
        heapify(i);
      }
      _returnedLast = END;
      return resetPosition();
    }
    return this;
  }

  protected void init() {
    for (int i = 0; i < _free; i++) {
      _heap[i] = null;
    }

    _heapSize = 0;
    _free = 0;
  }

  /* Build a heap in document order. put the smallest node on the top.
   * "smallest node" means the node before other nodes in document order
   */
  private void heapify(int i) {
    for (int r, l, smallest; ; ) {
      r = (i + 1) << 1;
      l = r - 1;
      smallest = l < _heapSize
          && _heap[l].isLessThan(_heap[i]) ? l : i;
      if (r < _heapSize && _heap[r].isLessThan(_heap[smallest])) {
        smallest = r;
      }
      if (smallest != i) {
        final HeapNode temp = _heap[smallest];
        _heap[smallest] = _heap[i];
        _heap[i] = temp;
        i = smallest;
      } else {
        break;
      }
    }
  }

  public void setMark() {
    for (int i = 0; i < _free; i++) {
      _heap[i].setMark();
    }
    _cachedReturnedLast = _returnedLast;
    _cachedHeapSize = _heapSize;
  }

  public void gotoMark() {
    for (int i = 0; i < _free; i++) {
      _heap[i].gotoMark();
    }
    // rebuild heap after call last() function. fix for bug 20913
    for (int i = (_heapSize = _cachedHeapSize) / 2; i >= 0; i--) {
      heapify(i);
    }
    _returnedLast = _cachedReturnedLast;
  }

  public DTMAxisIterator reset() {
    for (int i = 0; i < _free; i++) {
      _heap[i].reset();
      _heap[i].step();
    }

    // build heap
    for (int i = (_heapSize = _free) / 2; i >= 0; i--) {
      heapify(i);
    }

    _returnedLast = END;
    return resetPosition();
  }

}
